#define _CRT_SECURE_NO_WARNINGS 1
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
	struct ListNode* tail, * head = NULL;


	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;

	while (list1 != NULL && list2 != NULL)
	{
		if (list1->val < list2->val)
		{
			if (tail == NULL)
			{
				head = tail = list1;
			}
			else
			{
				tail->next = list1;
				tail = tail->next;
			}
			list1 = list1->next;
		}
		else
		{
			if (tail == NULL)
			{
				head = tail = list2;
			}
			else
			{
				tail->next = list2;
				tail = tail->next;
			}
			list2 = list2->next;
		}
	}

	// if(list1==NULL)
	// tail->next = list2;
	// if(list2==NULL)
	// tail->next = list1;

	if (list1)
		tail->next = list1;
	if (list2)
		tail->next = list2;


	return head;

}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
	struct ListNode* head1 = headA;
	struct ListNode* head2 = headB;

	int len1 = 1;
	int len2 = 1;

	while (head1->next != NULL)
	{
		len1++;
		head1 = head1->next;
	}

	while (head2->next != NULL)
	{
		len2++;
		head2 = head2->next;
	}

	// if(head1->val!=head2->val)
	// return NULL;

	if (head1 != head2)
		return NULL;

	int gap = abs(len1 - len2);
	struct ListNode* longlist = headA;
	struct ListNode* shortlist = headB;

	if (len1 < len2)
	{
		longlist = headB;
		shortlist = headA;
	}

	while (gap)
	{
		longlist = longlist->next;
		gap--;
	}

	while (longlist != shortlist)
	{
		longlist = longlist->next;
		shortlist = shortlist->next;
	}

	return longlist;



}